package org.example.myleet.p752;

import java.util.*;

public class Solution {

    private static final Map<String, String> FORWARD_NUMBERS = new HashMap<>();
    private static final Map<String, String> BACKWARD_NUMBERS = new HashMap<>();

    static {
        FORWARD_NUMBERS.put("0", "1");
        FORWARD_NUMBERS.put("1", "2");
        FORWARD_NUMBERS.put("2", "3");
        FORWARD_NUMBERS.put("3", "4");
        FORWARD_NUMBERS.put("4", "5");
        FORWARD_NUMBERS.put("5", "6");
        FORWARD_NUMBERS.put("6", "7");
        FORWARD_NUMBERS.put("7", "8");
        FORWARD_NUMBERS.put("8", "9");
        FORWARD_NUMBERS.put("9", "0");
        BACKWARD_NUMBERS.put("0", "9");
        BACKWARD_NUMBERS.put("1", "0");
        BACKWARD_NUMBERS.put("2", "1");
        BACKWARD_NUMBERS.put("3", "2");
        BACKWARD_NUMBERS.put("4", "3");
        BACKWARD_NUMBERS.put("5", "4");
        BACKWARD_NUMBERS.put("6", "5");
        BACKWARD_NUMBERS.put("7", "6");
        BACKWARD_NUMBERS.put("8", "7");
        BACKWARD_NUMBERS.put("9", "8");
    }

    public int openLock(String[] deadends, String target) {
        //对deadEnd进行哈希分析，方便判断死锁情况
        Set<String> deadEnds = new HashSet<>(Arrays.asList(deadends));
        //已经走过的节点，用于排除下一步的步数，防止死循环
        Set<String> visited = new HashSet<>(10000);
        //广度优先搜索
        int stepCount = 0;
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        while (!queue.isEmpty()) {
            Set<String> nextSteps = new HashSet<>(queue.size() * 2);
            while (!queue.isEmpty()) {
                String thisStep = queue.poll();
                if (deadEnds.contains(thisStep)) {
                    //进入死锁，此步不考虑
                    continue;
                }
                //检查是否到达目标位置
                if (thisStep.equals(target)) {
                    return stepCount;
                }
                visited.add(thisStep);
                //每个位置前后各拧一步
                for (int i = 0; i < 4; ++i) {
                    String thisStepI = thisStep.substring(i, i + 1);
                    String prefix = thisStep.substring(0, i);
                    String suffix = thisStep.substring(i + 1);
                    String forwardState = prefix + FORWARD_NUMBERS.get(thisStepI) + suffix;
                    if (!visited.contains(forwardState)) {
                        nextSteps.add(forwardState);
                    }
                    String backwardState = prefix + BACKWARD_NUMBERS.get(thisStepI) + suffix;
                    if (!visited.contains(backwardState)) {
                        nextSteps.add(backwardState);
                    }
                }
            }
            for (String nextStep : nextSteps) {
                queue.offer(nextStep);
            }
            ++stepCount;
        }
        return -1;
    }
}
